import java.util.HashMap;
import java.util.Map;

/**
 * 面试题48：最长不含重复字符的子字符串
 */
public class Offer_48 {
    /**
     * 方法二：滑动窗口
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(1)，ASCII 字符
     */
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int len = s.length();

        // key 为字符，value 为该字符最后一次出现的下标
        Map<Character, Integer> map = new HashMap<>();
        int ans = 0;
        // 双指针，子串从 left 开始，到 right 结束
        for (int left = 0, right = 0; right < len; right++) {
            char ch = s.charAt(right);
            // 如果当前字符已经重复，则将窗口左边收窄
            if (map.containsKey(ch)) {
                // 因为当前字符已出现重复，所以左边要从该字符上次出现的下一个位置开始
                left = Math.max(left, map.get(ch) + 1);
            }
            // 更新当前字符在字符串中的下标
            map.put(ch, right);
            // 更新无重复字符的最长子串的长度
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }

    /**
     * 方法一：动态规划 + 哈希表
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(1)，ASCII 字符
     */
    public int lengthOfLongestSubstring1(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int len = s.length();

        // 统计各字符最后一次出现的索引位置
        Map<Character, Integer> map = new HashMap<>();
        int ans = 0, temp = 0;
        for (int i = 0; i < len; i++) {
            char ch = s.charAt(i);
            // 通过访问哈希表获取最近的相同字符的索引 index
            int index = map.getOrDefault(ch, -1);
            // 更新哈希表
            map.put(ch, i);

            if (temp < i - index) {
                temp += 1;
            } else {
                temp = i - index;
            }
            ans = Math.max(ans, temp);
        }
        return ans;
    }
}
